package com.example.leetcode.trainingcamp.week3.expand;

import java.util.Stack;

/**
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 *
 * <p>求在该柱状图中，能够勾勒出来的矩形的最大面积。
 */
public class Test84 {

    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if (len == 0){
            return 0;
        }
        if (len == 1){
            return heights[0];
        }
        int max = Integer.MIN_VALUE;
        Stack<Integer> stack = new Stack<>();
        for (int i =0 ;i<len;i++){
            // 分层计算height
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]){
                int currHeight = heights[stack.pop()] ; //得到高度
                while (!stack.isEmpty() && heights[stack.peek()] == currHeight){
                    // 说明有高度相同的可以就将其抛出
                    stack.pop();
                }
                int weight;
                if (stack.isEmpty()){
                    // 当栈为空就说明，就说明为第一个元素就说明宽度为i 列如 2 2 2 1  就说明宽度为 3
                    weight = i;
                }else {
                    // 例如 2 2 1 2 2 2 1
                    weight = i - stack.peek() -1 ;
                }
                max = Math.max(max,weight*currHeight);
            }
            stack.push(i);
        }
        while (!stack.isEmpty()){
            int height = heights[stack.pop()];
            while (!stack.isEmpty() && heights[stack.peek()] == height){
                stack.pop();
            }
            int weight;
            if (stack.isEmpty()){
                // 栈为空 说明这个元素是栈里最低的元素，整个len 就是他的宽度
                weight = len;
            }else {
                weight = len - stack.peek() -1; // 说明夹在中间
            }
            max = Math.max(max,weight*height);
        }
        return max;
    }
}


class Demo84{
  public static void main(String[] args) {
    int[] heights = {2,1,5,6,2,3};
    Test84 t = new Test84();
    System.out.println(t.largestRectangleArea(heights));
  }
}